import java.util.Arrays;

/**
 * @Author @fiber-cloud
 * @Date 2025/8/17 10:08
 *
 */
public class TestHeap {
    public int[] elem;

    public int usedSize;//有效数据个数

    public static final int DEFAULT_SIZE = 10;

    public TestHeap(){
        elem = new int[DEFAULT_SIZE];
    }

    public void initElem(int[] a){
        for (int i = 0; i < a.length; i++) {
            elem[i] = a[i];
            usedSize++;
        }
    }
    
    //创建堆
    public void createHeap(){
        for (int parent = (usedSize-1-1)/2 ; parent >= 0 ;parent--){
            shiftDown(parent,usedSize);
        }
    }

    /**
     *
     * @param parent 每棵子树的根节点
     * @param len  每棵子树调整的结束位置 不能>len
     *             时间复杂度：O(log n)
     *  调整为大根堆，向下调整
     */
    private void shiftDown(int parent, int len) {
        int child = 2*parent+1;
        //1. 必须保证有左孩子
        while (child < len) {
            //child+1 < len && 保证有右孩子
            if(child+1 < len && elem[child] < elem[child+1]) {
                child++;
            }
            //child下标 一定是左右孩子 最大值的下标
           /* if(elem[child] < elem[child+1] && child+1 < len ) {
                child++;
            }*/
            if(elem[child] > elem[parent]) {
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                parent = child;
                child = 2*parent+1;
            }else {
                break;
            }
        }
    }

    //堆的插入 插入后依旧要保证还是一个大根堆
    public void offer(int val){
        if (isFull()){
            elem = Arrays.copyOf(this.elem,2*this.elem.length);
        }
        this.elem[usedSize] = val;
        usedSize++;
        //继续调整为大根堆
        shiftUp(usedSize-1);
    }

    //调整为大根堆，向上调整
    private void shiftUp(int i) {
        int parent = (i - 1)/2;
        while (i > 0){
            if (elem[i] > elem[parent]){
                int tmp = elem[i];
                elem[i] = elem[parent];
                elem[parent] = tmp;
                i = parent;
                parent = (i-1)/2;
            }else {
                break;
            }
        }
    }

    private boolean isFull() {
        return usedSize == elem.length;
    }

    //删除 删除的是堆顶元素
    public int pop(){
        if (isEmpty()){
            return -1;
        }
        //让堆顶元素与堆最后的元素进行交换，然后调整
        int tmp = elem[0];
        elem[0] = elem[usedSize-1];
        elem[usedSize-1] = tmp;
        usedSize--;
        //保证他仍然是一棵大根堆
        shiftDown(0,usedSize);
        return tmp;
    }

    private boolean isEmpty() {
        return usedSize == 0;
    }


}
